The present invention relates to parallelized processing in computer graphics, and particularly to rapidly assessing which patches of pixels are intersected by a particular fragment.
Background: 3D Computer Graphics
One of the driving features in the performance of most single-user computers is computer graphics. This is particularly important in computer games and workstations, but is generally very important across the personal computer market.
For some years the most critical area of graphics development has been in three-dimensional (“3D”) graphics. The peculiar demands of 3D graphics are driven by the need to present a realistic view, on a computer monitor, of a three-dimensional scene. The pattern written onto the two-dimensional screen must therefore be derived from the three-dimensional geometries in such a way that the user can easily “see” the three-dimensional scene (as if the screen were merely a window into a real three-dimensional scene). This requires extensive computation to obtain the correct image for display, taking account of surface textures, lighting, shadowing, and other characteristics.
The starting point (for the aspects of computer graphics considered in the present application) is a three-dimensional scene, with specified viewpoint and lighting (etc.). The elements of a 3D scene are normally defined by sets of polygons (typically triangles), each having attributes such as color, reflectivity, and spatial location. (For example, a walking human, at a given instant, might be translated into a few hundred triangles which map out the surface of the human's body.) Textures are “applied” onto the polygons, to provide detail in the scene. (For example, a flat carpeted floor will look far more realistic if a simple repeating texture pattern is applied onto it.) Designers use specialized modelling software tools, such as 3D Studio, to build textured polygonal models.
The 3D graphics pipeline consists of two major stages, or subsystems, referred to as geometry and rendering. The geometry stage is responsible for managing all polygon activities and for converting three-dimensional spatial data into a two-dimensional representation of the viewed scene, with properly-transformed polygons. The polygons in the three-dimensional scene, with their applied textures, must then be transformed to obtain their correct appearance from the viewpoint of the moment; this transformation requires calculation of lighting (and apparent brightness), foreshortening, obstruction, etc.
However, even after these transformations and extensive calculations have been done, there is still a large amount of data manipulation to be done: the correct values for EACH PIXEL of the transformed polygons must be derived from the two-dimensional representation. (This requires not only interpolation of pixel values within a polygon, but also correct application of properly oriented texture maps.) The rendering stage is responsible for these activities: it “renders” the two-dimensional data from the geometry stage to produce correct values for all pixels of each frame of the image sequence.
Since many aspects of 3D graphics require computations for many different data points, it is desirable to parallelize these computations where possible. The system described in the present application includes many features which support efficient parallelizing.
In the rendering process, one of the basic computational needs is determining whether a given pixel is part of a given primitive (e.g. a triangle). One of the basic ways to test this is with plane equations.
Each of the three sides of a triangle can be written as an equationAx+By+C=0.Each of the three equations for a given triangle can be converted into an inequality which will exclude points which are not in the triangle. When the coordinates of points are tested, only points which are within the triangle will meet all three conditions. (Similar tests can be applied for line segments and points (which can actually be treated as degenerate triangles), and for rectangles if needed.)
For example, take the simple case of a right triangle whose corners are at (0,0), (0,1), and (1,0). The three corresponding plane equations are then:x+y−1=0x=0 andy=0.If the triangle includes all of its borders, the corresponding inequalities would be(x+y−1)≦0x≧0y≧0.A pixel (x,y) is part of this particular triangle if and only if all three of these inequalities are true. Thus the logical values of these inequalities can be ANDed to get a true/false test of pixel membership.
Note that, if the same triangle is farther from the origin, the numbers in the equation may be larger. For example, if the same triangle has its lower left corner at (60000,60000), the corresponding inequalities will bex+y−120001≦0x−60000≧0y−60000≧0.Tile Relative Origin for Plane Equations
The present inventor has realized that, when rendering operations are parallelized, there is a particular advantage to computing plane-equation membership tests as offsets to a base point which is within or adjacent to the patch of pixels being tested. This reduces the required dynamic range for the constant term in membership computations, and simplifies the hardware requirements.
The disclosed innovations, in various embodiments, provide one or more of at least the following advantages:    rapid parallelized membership testing    reduced hardware requirements.